package com.congee02;

import java.util.Arrays;

public class MinPathSum_Cache {

    public int minPathSum(int[][] grid) {

        for (int[] c : cache) {
            Arrays.fill(c, -1);
        }

        int m = grid.length;
        int n = grid[0].length;
        return process(grid, m, n, 0, 0);
    }

    private int[][] cache = new int[201][201];
    private int process(int[][] grid, int m, int n, int x, int y) {
        if (x >= m || y >= n) {
            return 201 * 200;
        }
        if (x ==  m - 1 && y == n - 1) {
            return grid[m - 1][n - 1];
        }
        if (cache[x][y] == -1) {
            cache[x][y] = grid[x][y] + Math.min(
                    process(grid, m, n, x + 1, y),
                    process(grid, m, n, x, y + 1)
            );
        }
        return cache[x][y];
    }

    public static void main(String[] args) {
        MinPathSum_Cache s = new MinPathSum_Cache();
        System.out.println(s.minPathSum(
                new int[][]{
                        {5, 1},
                        {2, 1}
                }
        ));
    }

}
